#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
LFUCache(3)
set(2, 2)
set(1, 1)
get(2)
get(1)
get(2)
set(3, 3)
set(4, 4)
get(3)
get(2)
get(1)
get(4)
"""
import collections


class Node:
    def __init__(self, key, value, freq=0):
        self.key   = key
        self.value = value
        self.freq = freq


class List:
    def __init__(self):
        self.l = collections.OrderedDict()

    def add(self, n):
        self.l[n.key] = n

    def del_tail(self):
        key, n = self.l.popitem(last=False)      # 头部优先级最低, 弹出
        return n

    def del_node(self, n):
        del self.l[n.key]

    def len(self):
        return len(self.l)


class LFUCache:
    """
    @param: capacity: An integer
    """
    def __init__(self, capacity):
        self.capacity = capacity

        self.freqs = collections.OrderedDict()       # {freq : List}
        self.map = {}       # {key : node}
        self.min_freq = 999

    def len(self):
        return len(self.map)

    def full(self):
        return self.len() >= self.capacity

    def set(self, key, value):
        n = self.map.get(key)

        if key == 4:
            print("4 -------------------  ---------------------", n)

        if n is None:
            # 判断capacity
            n = Node(key, value)
            # 添加

            if key == 4:
                print('4 full -------------------  ---------------------', self.full())
                print('4 keys -------------------  ---------------------', list(self.map.keys()))

            if self.full():
                del_tail = self.del_tail()
                if key == 4:
                    print("4 tail", del_tail.key)

            # assert n.key ==
            if n.key == 3:
                print("3 ------------------- set freq---------------------", n.freq)
            self.add_head(n)
            # self.min_freq = 0
            # self.add_node(n)
        else:
            freq = n.freq
            self.del_node(n)

            n.freq, n.value = freq + 1, value
            # self.get_and_create_if_absence(n.freq).add(n)
            self.add_node(n)

    def get_and_create_if_absence(self, freq):
        lst = self.freqs.get(freq)
        if lst is None:
            lst = List()
            self.freqs[freq] = lst

        return lst

    def add_head(self, n):
        self.get_and_create_if_absence(0).add(n)
        self.map[n.key] = n
        self.min_freq = 0

    def del_node(self, n):
        freq = n.freq
        # lst = self.freqs[freq]
        lst = self.get_and_create_if_absence(freq)
        lst.del_node(n)

        if lst.len() == 0:
            del self.freqs[freq]

        del self.map[n.key]

    def del_tail(self):
        assert self.len() > 0
        # self.get_and_create_if_absence[]

        # self.min_freq = next(iter(self.freqs.keys()))
        lst = self.get_and_create_if_absence(self.min_freq)
        n = lst.del_tail()

        print('del tail freq', self.min_freq, n.key, n.value)

        if lst.len() == 0:
            del self.freqs[self.min_freq]

        del self.map[n.key]

        return n

    def has_freq(self, freq):
        return freq in self.freqs

    def add_node(self, n):
        if n.key == 4:
            # print('4, pre -------------------  ---------------------', n.freq-1, self.get_and_create_if_absence(0).len())
            print('4, pre -------------------  ---------------------', n.freq-1, self.has_freq(n.freq-1))
        freq = n.freq

        self.get_and_create_if_absence(freq).add(n)
        self.map[n.key] = n

        self.update_min_freq(freq)

    def update_min_freq(self, freq):
        if freq == 0:
            self.min_freq = 0
        else:
            # if self.min_freq == freq-1 and self.get_and_create_if_absence(freq-1) is None:
            if self.min_freq == freq-1 and not self.has_freq(freq-1):
                self.min_freq = freq

    def get(self, key):
        n = self.map.get(key)
        if n is None:
            return -1

        # if key == 2:
        #     print('2 freq ', n.freq)

        # if key == 1:
        #     print('1 freq ', n.freq)

        self.del_node(n)

        n.freq += 1
        if key == 4:
            print('4 new freq -------------------  ---------------------', n.freq)
        self.add_node(n)


        return n.value

    # def show(self):
    #     print('=================== hash  [%s] =====================' % self.hash)
    #     print('=================== stack [%s] =====================' % self.stack)


def main():
    print("start main")
    test2()

def test():
    s = LFUCache(4)
    s.set(2, 2)
    s.set(3, 3)
    s.set(4, 4)
    s.set(5, 5)
    # s.show()

    print(s.get(3))
    print(s.get(2))
    print(s.get(4))
    print(s.get(5))

def test2():
    s = LFUCache(3)
    s.set(2, 2)
    s.set(1, 1)
    print(s.get(2))
    print(s.get(1))
    print(s.get(2))
    print(s.get(1))

    s.set(3, 3)
    s.set(4, 4)
    print(s.get(3))
    print(s.get(2))
    print(s.get(1))
    print(s.get(4))
    print(s.min_freq)

if __name__ == "__main__":
    main()
